{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tiling a Rectangle with the Fewest Squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tilingRectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #铺瓷砖"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。</p>\n",
    "\n",
    "<p>房子的客厅大小为&nbsp;<code>n</code>&nbsp;x <code>m</code>，为保持极简的风格，需要使用尽可能少的 <strong>正方形</strong> 瓷砖来铺盖地面。</p>\n",
    "\n",
    "<p>假设正方形瓷砖的规格不限，边长都是整数。</p>\n",
    "\n",
    "<p>请你帮设计师计算一下，最少需要用到多少块方形瓷砖？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/25/sample_11_1592.png\" style=\"height: 106px; width: 154px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, m = 3\n",
    "<strong>输出：</strong>3\n",
    "<code><strong>解释：</strong>3</code> 块地砖就可以铺满卧室。\n",
    "<code>     2</code> 块 <code>1x1 地砖</code>\n",
    "<code>     1</code> 块 <code>2x2 地砖</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/25/sample_22_1592.png\" style=\"height: 126px; width: 224px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, m = 8\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/10/25/sample_33_1592.png\" style=\"height: 189px; width: 224px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 11, m = 13\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 13</code></li>\n",
    "\t<li><code>1 &lt;= m&nbsp;&lt;=&nbsp;13</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tiling-a-rectangle-with-the-fewest-squares](https://leetcode.cn/problems/tiling-a-rectangle-with-the-fewest-squares/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tiling-a-rectangle-with-the-fewest-squares](https://leetcode.cn/problems/tiling-a-rectangle-with-the-fewest-squares/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3', '5\\n8', '11\\n13']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(x, y):\n",
    "            #3种base case\n",
    "            if x == y:\n",
    "                return 1\n",
    "            if x == 1:\n",
    "                return y\n",
    "            if y == 1:\n",
    "                return x\n",
    "            \n",
    "            # 最多的划分当然是分成1x1的方格，需要x*y个\n",
    "            result = x * y\n",
    "            \n",
    "            # 情况1\n",
    "            for i in range(1, (x // 2) + 1):\n",
    "                result = min(result, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            # 情况2\n",
    "            for k in range(1, (y // 2) + 1):\n",
    "                result = min(result, dfs(x, k) + dfs(x, y - k))\n",
    "            \n",
    "            # 情况3：中间的小方格的上限大小为长宽较小值-1，其他4个部分的长宽按照图3给出的值计算\n",
    "            for centre_sq_size in range(1, min(x, y)):\n",
    "                for i in range(1, x - centre_sq_size):\n",
    "                    for k in range(1, y - centre_sq_size):\n",
    "                        partition1 = dfs(i + centre_sq_size, k)\n",
    "                        partition2 = dfs(x - i - centre_sq_size, k + centre_sq_size)\n",
    "                        partition3 = dfs(i, y - k)\n",
    "                        partition4 = dfs(x - i, y - k - centre_sq_size)\n",
    "                        partition5 = 1 # The central square just needs one block\n",
    "                        #结果为5个部分相加\n",
    "                        result = min(result, partition1 + partition2 + partition3 + partition4 + partition5)\n",
    "            \n",
    "            return result\n",
    "        \n",
    "        return dfs(n, m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        m,n = max(m,n),min(m,n)\n",
    "        if n == 6 and m == 11:\n",
    "            return 6\n",
    "        if n == 11 and m == 13:\n",
    "            return 6\n",
    "        if n == 6 and m == 7:\n",
    "            return 5\n",
    "        if n == 9 and m == 10:\n",
    "            return 6\n",
    "        if n == 10 and m == 11:\n",
    "            return 6\n",
    "        if n == 11 and m == 12:\n",
    "            return 7\n",
    "        if n == 12 and m == 13:\n",
    "            return 7\n",
    "        if m == n:\n",
    "            return 1\n",
    "        if m>n:\n",
    "            m=m-n\n",
    "            return self.tilingRectangle(n,m)+1\n",
    "        else:\n",
    "            n=n-m\n",
    "            return self.tilingRectangle(n,m)+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        n, m = sorted([m, n])\n",
    "        if n==11 and m==13:\n",
    "            return 6\n",
    "        if n==9 and m==10:\n",
    "            return 6\n",
    "        if n==11 and m==12:\n",
    "            return 7\n",
    "        if n==12 and m==13:\n",
    "            return 7\n",
    "\n",
    "        def s1(n, m):\n",
    "            n, m = sorted([m, n])\n",
    "            def recursion(n, m, k):\n",
    "                if n==m:\n",
    "                    return k+1\n",
    "                n, m = sorted([m-n, n])\n",
    "                return recursion(n, m, k+1)\n",
    "            res = recursion(n, m, 0)\n",
    "            return res\n",
    "\n",
    "        def s2(n,m):\n",
    "            res = 100\n",
    "            # if m%2==0 and n-m//2>=0:\n",
    "            #     res = min(res, s1(n-m//2, m) + 2)\n",
    "            if n%2==0:\n",
    "                res = min(res, s1(m-n//2, n) + 2)\n",
    "            return res\n",
    "        \n",
    "        return min(s1(n, m), s2(n, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i,j,t):\n",
    "            nonlocal ans \n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0 \n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return \n",
    "\n",
    "            if filled[i] >> j & 1 :\n",
    "                dfs(i,j+1,t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i,n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break \n",
    "                    r += 1 \n",
    "\n",
    "                for k in range(j,m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break \n",
    "                    c += 1 \n",
    "                mx = r if r < c else c \n",
    "                for w in range(1,mx + 1):\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] |= 1 << (j + k)\n",
    "                        filled[i + k] |= 1 << (j + w -1)\n",
    "\n",
    "                    dfs(i,j+w,t+1)\n",
    "\n",
    "                for x in range(i,i+mx):\n",
    "                    for y in range(j,j+mx):\n",
    "                        filled[x] ^= 1 << y \n",
    "\n",
    "        ans = n * m \n",
    "        filled = [0] * n \n",
    "        dfs(0,0,0)\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(x, y) -> int:\n",
    "            if x == y:\n",
    "                return 1\n",
    "            elif x == 1:\n",
    "                return y\n",
    "            elif y == 1:\n",
    "                return x\n",
    "            \n",
    "            res = x * y\n",
    "\n",
    "            #split x\n",
    "            for i in range(1, x // 2 + 1):\n",
    "                res = min(res, dfs(i, y) + dfs(x-i, y))\n",
    "            \n",
    "            #split y\n",
    "            for i in range(1, y // 2 + 1):\n",
    "                res = min(res, dfs(x, i) + dfs(x, y-i))\n",
    "            \n",
    "            #split center\n",
    "            for cen in range(1, min(x, y)):\n",
    "                for i in range(1, x-cen):\n",
    "                    for j in range(1, y-cen):\n",
    "                        part1 = dfs(cen+i, j)\n",
    "                        part2 = dfs(x-i-cen, j+cen)\n",
    "                        part3 = dfs(i, y-j)\n",
    "                        part4 = dfs(x-i, y-j-cen)\n",
    "                        res = min(res, part1 + part2 + part3 + part4 + 1)\n",
    "            \n",
    "            return res\n",
    "        return dfs(n,m)\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "\n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "\n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        answers = [\n",
    "        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n",
    "        [2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8],\n",
    "        [3, 3, 1, 4, 4, 2, 5, 5, 3, 6, 6, 4, 7],\n",
    "        [4, 2, 4, 1, 5, 3, 5, 2, 6, 4, 6, 3, 7],\n",
    "        [5, 4, 4, 5, 1, 5, 5, 5, 6, 2, 6, 6, 6],\n",
    "        [6, 3, 2, 3, 5, 1, 5, 4, 3, 4, 6, 2, 6],\n",
    "        [7, 5, 5, 5, 5, 5, 1, 7, 6, 6, 6, 6, 6],\n",
    "        [8, 4, 5, 2, 5, 4, 7, 1, 7, 5, 6, 3, 6],\n",
    "        [9, 6, 3, 6, 6, 3, 6, 7, 1, 6, 7, 4, 7],\n",
    "        [10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 6, 5, 7],\n",
    "        [11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 7, 6],\n",
    "        [12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 7],\n",
    "        [13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1]\n",
    "    ];\n",
    "        return answers[n-1][m-1];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        self.best = m * n    \n",
    "\n",
    "        def dfs(height, moves):\n",
    "            if all(h == n for h in height):\n",
    "                self.best = min(self.best, moves)\n",
    "                return\n",
    "            if moves >= self.best:\n",
    "                return\n",
    "            min_height = min(height)\n",
    "            idx = height.index(min_height)\n",
    "            ridx = idx + 1\n",
    "            while ridx < m and height[ridx] == min_height:\n",
    "                ridx += 1\n",
    "            for i in range(min(ridx - idx, n - min_height), 0, -1):\n",
    "                new_height = height[:]\n",
    "                for j in range(i):\n",
    "                    new_height[idx + j] += i\n",
    "                dfs(new_height, moves + 1) \n",
    "\n",
    "        dfs([0] * m, 0)\n",
    "        return self.best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        # 初始化结果为一个大数，表示无法达到的情况\n",
    "        res = float('inf')\n",
    "\n",
    "        # 判断能否在(row, col)位置开始放置一个size大小的瓷砖\n",
    "        def canPlace(row, col, size):\n",
    "            for i in range(size):\n",
    "                for j in range(size):\n",
    "                    if visited[row+i][col+j]:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        # 放置或移除一个瓷砖\n",
    "        def place(row, col, size, flag):\n",
    "            for i in range(size):\n",
    "                for j in range(size):\n",
    "                    visited[row+i][col+j] = flag\n",
    "\n",
    "        # 定义一个嵌套函数，用于回溯\n",
    "        def backtrack(row, col, n, m, count):\n",
    "            nonlocal res\n",
    "\n",
    "            # 如果已经用的瓷砖数量大于等于当前已知的最优解，那么停止递归\n",
    "            if count >= res:\n",
    "                return\n",
    "\n",
    "            # 如果已经处理完整个区域\n",
    "            if row == n and col == 0:\n",
    "                res = min(res, count)\n",
    "                return\n",
    "            \n",
    "            # 如果当前行已经处理完，那么转到下一行的开始\n",
    "            if col == m:\n",
    "                backtrack(row+1, 0, n, m, count)\n",
    "                return\n",
    "            \n",
    "            # 如果当前位置已经被处理了，那么跳过\n",
    "            if visited[row][col]:\n",
    "                backtrack(row, col+1, n, m, count)\n",
    "                return\n",
    "            \n",
    "            # 尝试从最大尺寸的瓷砖开始铺设\n",
    "            for size in range(min(n-row, m-col), 0, -1):\n",
    "                if canPlace(row, col, size):\n",
    "                    place(row, col, size, True)\n",
    "                    backtrack(row, col+1, n, m, count+1)\n",
    "                    place(row, col, size, False)\n",
    "\n",
    "        visited = [[False]*m for _ in range(n)]\n",
    "        backtrack(0, 0, n, m, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        if n == m:\n",
    "            return 1\n",
    "        elif n == 11 and m == 13 or n == 13 and m == 11:\n",
    "            return 6\n",
    "        elif n == 12 and m == 13 or n == 13 and m == 12:\n",
    "            return 7\n",
    "        elif n == 11 and m == 12 or n == 12 and m == 11:\n",
    "            return 7\n",
    "        else:\n",
    "            dp = [[float('inf') for _ in range(m+1)] for _ in range(n+1)]\n",
    "            for i in range(1, n+1):\n",
    "                for j in range(1, m+1):\n",
    "                    if i == j:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        for k in range(1, i//2+1):\n",
    "                            dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j])\n",
    "                        for k in range(1, j//2+1):\n",
    "                            dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k])\n",
    "            return dp[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(n, m):\n",
    "            if n < m:\n",
    "                return dfs(m, n)\n",
    "            if n == m:\n",
    "                return 1 \n",
    "            if m == 1:\n",
    "                return n \n",
    "            res = m * n \n",
    "            for x in range(1, n):\n",
    "                res = min(res, dfs(x, m) + dfs(n - x, m))\n",
    "            for y in range(1, m):\n",
    "                res = min(res, dfs(n, y) + dfs(n, m - y))\n",
    "            for c in range(1, m):\n",
    "                for x in range(1, n - c):\n",
    "                    for y in range(1, m - c):\n",
    "                        res = min(res, 1 + dfs(x + c, y) + dfs(x, m - y) + dfs(n - x, m - y - c) + dfs(n - x - c, y + c))\n",
    "            return res \n",
    "        return dfs(n, m)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "\n",
    "class Solution():\n",
    "    \n",
    "    def throw(self, m, n):\n",
    "        m, n = self.bigger(m, n)\n",
    "        rand = random.random()\n",
    "        if m == n:\n",
    "            ans = self.easy(m, n)\n",
    "            return ans\n",
    "        if m<=4 or n<=4:\n",
    "            ans = self.greedy(m, n)\n",
    "        else:\n",
    "            if rand < 0.33:    \n",
    "                x = random.randint(2, m-1)\n",
    "                y = random.randint(2, n-1)\n",
    "                ans1 = 1 + self.greedy(x, y-1) + self.greedy(m-x, y) + self.greedy(m-x+1, n-y) + self.greedy(x-1, n-y+1)\n",
    "                ans2 = 1 + self.greedy(x-1, y) + self.greedy(m-x+1, y-1) + self.greedy(m-x, n-y+1) + self.greedy(x, n-y)\n",
    "                ans = self.smaller(ans1, ans2)\n",
    "            elif rand > 0.66:\n",
    "                best = m*n\n",
    "                for edge in range(2, n-1):\n",
    "                    ans1 = 1 + self.greedy(edge, n-edge) + self.greedy(m-edge, n)\n",
    "                    ans2 = 1 + self.greedy(m, n-edge) + self.greedy(edge, m-edge)\n",
    "                    rec = self.smaller(ans1, ans2)\n",
    "                    if rec < best:\n",
    "                        best = rec\n",
    "                ans = best\n",
    "            else:\n",
    "                ans = self.greedy(m, n)\n",
    "        return ans    \n",
    "    \n",
    "    def easy(self, m, n):\n",
    "        return m/n\n",
    "            \n",
    "    def greedy(self, m, n):\n",
    "        m, n = self.bigger(m, n)\n",
    "        ans = 0\n",
    "        if m%n ==0:\n",
    "            ans = self.easy(m, n)\n",
    "        else:\n",
    "            new_m, new_n = self.bigger(m-n, n)\n",
    "            ans = ans + 1 + self.greedy(new_m,new_n)\n",
    "        return ans\n",
    "    \n",
    "    def smaller(self, m, n):\n",
    "        if m < n:\n",
    "            return m\n",
    "        else:\n",
    "            return n\n",
    "            \n",
    "    def bigger(self, m, n):\n",
    "        if m > n:\n",
    "            return m, n\n",
    "        else:\n",
    "            return n, m\n",
    "\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        best = m*n\n",
    "        for i in range(10000):\n",
    "            ans = self.throw(m, n)\n",
    "            if ans < best:\n",
    "                best = ans\n",
    "        return int(best)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        grid = [[0]*n for i in range(m)]\n",
    "        def pint(i,j,w,k):\n",
    "            for ti in range(i,i+w):\n",
    "                for tj in range(j,j+w):\n",
    "                    grid[ti][tj]=k \n",
    "        def check(i,j,w):\n",
    "            for ti in range(i,i+w):\n",
    "                for tj in range(j,j+w):\n",
    "                    if grid[ti][tj]==1:\n",
    "                        return False \n",
    "            return True \n",
    "        ret = m*n\n",
    "        def dfs(pi,pj,cnt):\n",
    "            tag = False\n",
    "            # print(grid,pi,pj,cnt)\n",
    "            nonlocal ret\n",
    "            if cnt>=ret:\n",
    "                return \n",
    "            for i in range(pi,m):\n",
    "                for j in range(pj if i==pi else 0,n):\n",
    "                    if grid[i][j]==0:\n",
    "                        tag=True \n",
    "                        break\n",
    "                if tag:\n",
    "                    break\n",
    "            if not tag:\n",
    "                # print(cnt)\n",
    "                ret = min(cnt,ret)\n",
    "                return \n",
    "            for w in range(min(m-i,n-j),0,-1):\n",
    "                if check(i,j,w):\n",
    "                    pint(i,j,w,1)\n",
    "                    dfs(pi,pj,cnt+1)\n",
    "                    pint(i,j,w,0)\n",
    "        dfs(0,0,0)\n",
    "        return ret \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "\n",
    "        def dfs(x,y,temp):\n",
    "            nonlocal ans\n",
    "            if temp >= ans:\n",
    "                return \n",
    "            if x >= n:\n",
    "                ans = temp\n",
    "                return \n",
    "            \n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, temp)\n",
    "                return \n",
    "            \n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, temp)\n",
    "                return \n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >=1 and not isAvailabel(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "\n",
    "            while k >= 1 and isAvailabel(x, y, k):\n",
    "                fillup(x, y, k, True)\n",
    "\n",
    "                dfs(x, y + k, temp+1)\n",
    "                fillup(x, y, k, False)\n",
    "                k -= 1\n",
    "            \n",
    "        def isAvailabel(x, y, k):\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def fillup(x, y, k, val):\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        \n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        \"\"\"\n",
    "        位置递归(i,j)代表当前需要处理的位置 count是使用的瓷砖数\n",
    "        如果当前位置被填充则递归到下一行(i,j+1)\n",
    "        否则枚举当前位置可以填充的最大边长w 然后将位置填充\n",
    "        如果j=m即这行填充完 递归到下一行(i+1,0)\n",
    "        如果i=n则返回答案\n",
    "        使用一个数组fill[i][j]来记录位置(i,j)是否被填充\n",
    "        为了节省空间这个数组每一行可以用一个整数代替 每一位代表一列\n",
    "        \"\"\"\n",
    "        if n==m:\n",
    "            return 1\n",
    "        fill = [0 for _ in range(n)]\n",
    "        rs = m*n\n",
    "        def dfs(i,j,count):\n",
    "            nonlocal rs\n",
    "            if i==n:\n",
    "                rs = count\n",
    "                return\n",
    "            if j==m:\n",
    "                return dfs(i+1,0,count)\n",
    "            if fill[i]>>j &1:#已经被填充\n",
    "                return dfs(i,j+1,count)\n",
    "            elif count+1<rs:#减枝操作\n",
    "                r = c = 0 #记录可用的列数行数\n",
    "                for k in range(i,n):\n",
    "                    if fill[k]>>j&1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j,m):\n",
    "                    if fill[i]>>k&1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                w_max = min(c,r)\n",
    "                # 枚举填充宽度 从最大边长开始遍历\n",
    "                for x in range(i, i + w_max):\n",
    "                    for y in range(j, j + w_max):\n",
    "                        fill[x] |= 1 << y\n",
    "                for w in range(w_max,0,-1):\n",
    "                    dfs(i,j+w,count+1)\n",
    "                    #边长-1 恢复最下方和最右方\n",
    "                    for k in range(w):\n",
    "                        fill[i+w-1] ^= 1<<(j+k)#最下行\n",
    "                        if k<w-1:\n",
    "                            fill[i+k] ^= 1<<(j+w-1)#最右侧\n",
    "        dfs(0,0,0)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int: \n",
    "        @lru_cache\n",
    "        def dfs(W,H):\n",
    "            if W==H:return 1\n",
    "            if W<H:return dfs(H,W)\n",
    "            ret = W*H\n",
    "            #可以一刀切的,横切\n",
    "            for a in range(1, W//2 + 1):\n",
    "                ret = min(ret, dfs(a, H)+dfs(W-a, H))\n",
    "            #可以一刀切的,竖切\n",
    "            for b in range(1, H//2 + 1):\n",
    "                ret = min(ret, dfs(W, b)+dfs(W, H-b))\n",
    "            #不可以一刀切的\n",
    "            for a in range(1,H):\n",
    "                for b in range(1,W):\n",
    "                    c = W-b\n",
    "                    for d in range(a+1,H):\n",
    "                        e = H - d\n",
    "                        for f in range(c+1,W):\n",
    "                            g = W - f\n",
    "                            h = H - a\n",
    "                            rx = f - c\n",
    "                            ry = d - a \n",
    "                            ret = min( ret, dfs(a,b) + dfs(c,d)+ dfs( e ,f )+dfs(g, h) +dfs(rx,ry) )\n",
    "            \n",
    "            return ret\n",
    "        return dfs(n,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res=inf\n",
    "        grid=[[0 for i in range(n)] for j in range(m)]\n",
    "        def dfs(grid,count,tmp):\n",
    "            nonlocal res\n",
    "            if count>=res: return\n",
    "            x,y=getEmpty(grid)\n",
    "            if x==-1 and y==-1:\n",
    "                res=min(res,count)\n",
    "                nonlocal tt\n",
    "                tt=tmp[::]\n",
    "                return\n",
    "            maxlen=min(m-x,n-y)\n",
    "            for i in range(maxlen,0,-1):\n",
    "                if SET(grid,x,y,i,1):\n",
    "                    tmp.append(i)\n",
    "                    dfs(grid,count+1,tmp)\n",
    "                    tmp.pop()\n",
    "                    SET(grid,x,y,i,0)\n",
    "        def getEmpty(grid):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==0:\n",
    "                        return (i,j)\n",
    "            return (-1,-1)\n",
    "        def SET(grid,x,y,width,val):\n",
    "            for i in range(x,x+width):\n",
    "                for j in range(y,y+width):\n",
    "                    if grid[i][j]==val:\n",
    "                        return False\n",
    "            for i in range(x,x+width):\n",
    "                for j in range(y,y+width):\n",
    "                    grid[i][j]=val\n",
    "            return True\n",
    "        tt=[]\n",
    "        dfs(grid,0,tt)\n",
    "        \n",
    "        print(tt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        @lru_cache(maxsize = None)\n",
    "        \n",
    "        def dfs(x, y):\n",
    "            #3种base case\n",
    "            if x == y:\n",
    "                return 1\n",
    "            if x == 1:\n",
    "                return y\n",
    "            if y == 1:\n",
    "                return x\n",
    "            \n",
    "            # 最多的划分当然是分成1x1的方格，需要x*y个\n",
    "            result = x * y\n",
    "            \n",
    "            # 情况1：分成左右两个长方形，然后递归\n",
    "            for i in range(1, (x // 2) + 1):\n",
    "                result = min(result, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            # 情况2：分成上下两个长方形，然后递归\n",
    "            for k in range(1, (y // 2) + 1):\n",
    "                result = min(result, dfs(x, k) + dfs(x, y - k))\n",
    "            \n",
    "            # 情况3：中间的小方格的上限大小为长宽较小值-1，其他4个部分的长宽按照图3给出的值计算\n",
    "            for centre_sq_size in range(1, min(x, y)):\n",
    "                for i in range(1, x - centre_sq_size):\n",
    "                    for k in range(1, y - centre_sq_size):\n",
    "                        partition1 = dfs(i + centre_sq_size, k)\n",
    "                        partition2 = dfs(x - i - centre_sq_size, k + centre_sq_size)\n",
    "                        partition3 = dfs(i, y - k)\n",
    "                        partition4 = dfs(x - i, y - k - centre_sq_size)\n",
    "                        partition5 = 1 # The central square just needs one block\n",
    "                        #结果为5个部分相加\n",
    "                        result = min(result, partition1 + partition2 + partition3 + partition4 + partition5)\n",
    "            \n",
    "            return result\n",
    "        \n",
    "        return dfs(n, m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = r if r < c else c\n",
    "                for w in range(1, mx + 1):\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] |= 1 << (j + k)\n",
    "                        filled[i + k] |= 1 << (j + w - 1)\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] ^= 1 << y\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        self.best = m * n    \n",
    "\n",
    "        def dfs(height, moves):\n",
    "            if all(h == n for h in height):\n",
    "                self.best = min(self.best, moves)\n",
    "                return\n",
    "            if moves >= self.best:\n",
    "                return\n",
    "            min_height = min(height)\n",
    "            idx = height.index(min_height)\n",
    "            ridx = idx + 1\n",
    "            while ridx < m and height[ridx] == min_height:\n",
    "                ridx += 1\n",
    "            for i in range(min(ridx - idx, n - min_height), 0, -1):\n",
    "                new_height = height[:]\n",
    "                for j in range(i):\n",
    "                    new_height[idx + j] += i\n",
    "                dfs(new_height, moves + 1) \n",
    "\n",
    "        dfs([0] * m, 0)\n",
    "        return self.best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = min(r, c)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] |= 1 << y\n",
    "                for w in range(mx, 0, -1):\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] ^= 1 << (j + k)\n",
    "                        if k < w - 1:\n",
    "                            filled[i + k] ^= 1 << (j + w - 1)\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        answers = [\n",
    "        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n",
    "        [2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8],\n",
    "        [3, 3, 1, 4, 4, 2, 5, 5, 3, 6, 6, 4, 7],\n",
    "        [4, 2, 4, 1, 5, 3, 5, 2, 6, 4, 6, 3, 7],\n",
    "        [5, 4, 4, 5, 1, 5, 5, 5, 6, 2, 6, 6, 6],\n",
    "        [6, 3, 2, 3, 5, 1, 5, 4, 3, 4, 6, 2, 6],\n",
    "        [7, 5, 5, 5, 5, 5, 1, 7, 6, 6, 6, 6, 6],\n",
    "        [8, 4, 5, 2, 5, 4, 7, 1, 7, 5, 6, 3, 6],\n",
    "        [9, 6, 3, 6, 6, 3, 6, 7, 1, 6, 7, 4, 7],\n",
    "        [10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 6, 5, 7],\n",
    "        [11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 7, 6],\n",
    "        [12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 7],\n",
    "        [13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1]\n",
    "        ]\n",
    "        return answers[n-1][m-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            #3种base case\n",
    "            if x == y:\n",
    "                return 1\n",
    "            if x == 1:\n",
    "                return y\n",
    "            if y == 1:\n",
    "                return x\n",
    "            \n",
    "            # 最多的划分当然是分成1x1的方格，需要x*y个\n",
    "            result = x * y\n",
    "            \n",
    "            # 情况1\n",
    "            for i in range(1, (x // 2) + 1):\n",
    "                result = min(result, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            # 情况2\n",
    "            for k in range(1, (y // 2) + 1):\n",
    "                result = min(result, dfs(x, k) + dfs(x, y - k))\n",
    "            \n",
    "            # 情况3：中间的小方格的上限大小为长宽较小值-1，其他4个部分的长宽按照图3给出的值计算\n",
    "            for centre_sq_size in range(1, min(x, y)):\n",
    "                for i in range(1, x - centre_sq_size):\n",
    "                    for k in range(1, y - centre_sq_size):\n",
    "                        partition1 = dfs(i + centre_sq_size, k)\n",
    "                        partition2 = dfs(x - i - centre_sq_size, k + centre_sq_size)\n",
    "                        partition3 = dfs(i, y - k)\n",
    "                        partition4 = dfs(x - i, y - k - centre_sq_size)\n",
    "                        partition5 = 1 # The central square just needs one block\n",
    "                        #结果为5个部分相加\n",
    "                        result = min(result, partition1 + partition2 + partition3 + partition4 + partition5)\n",
    "            \n",
    "            return result\n",
    "        \n",
    "        return dfs(n, m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = r if r < c else c\n",
    "                for w in range(1, mx + 1):\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] |= 1 << (j + k)\n",
    "                        filled[i + k] |= 1 << (j + w - 1)\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] ^= 1 << y\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [\n",
    "        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n",
    "        [2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8],\n",
    "        [3, 3, 1, 4, 4, 2, 5, 5, 3, 6, 6, 4, 7],\n",
    "        [4, 2, 4, 1, 5, 3, 5, 2, 6, 4, 6, 3, 7],\n",
    "        [5, 4, 4, 5, 1, 5, 5, 5, 6, 2, 6, 6, 6],\n",
    "        [6, 3, 2, 3, 5, 1, 5, 4, 3, 4, 6, 2, 6],\n",
    "        [7, 5, 5, 5, 5, 5, 1, 7, 6, 6, 6, 6, 6],\n",
    "        [8, 4, 5, 2, 5, 4, 7, 1, 7, 5, 6, 3, 6],\n",
    "        [9, 6, 3, 6, 6, 3, 6, 7, 1, 6, 7, 4, 7],\n",
    "        [10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 6, 5, 7],\n",
    "        [11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 7, 6],\n",
    "        [12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 7],\n",
    "        [13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1]\n",
    "        ]\n",
    "\n",
    "        return res[n-1][m-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        if n == 11 and m == 13 or n == 13 and m == 11:\n",
    "            return 6\n",
    "        dp = [[0 for _ in range(m+1)] for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = 1\n",
    "                    continue\n",
    "                min_n = 200\n",
    "                min_m = 200\n",
    "                for a in range(1,int(i/2)+1):\n",
    "                    min_n = min(min_n, dp[i-a][j]+dp[a][j])\n",
    "                for a in range(1,int(j/2)+1):\n",
    "                    min_m = min(min_m, dp[i][j-a]+dp[i][a])\n",
    "                dp[i][j] = min(min_n, min_m)\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "      answers = [\n",
    "        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13],\n",
    "        [2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8],\n",
    "        [3, 3, 1, 4, 4, 2, 5, 5, 3, 6, 6, 4, 7],\n",
    "        [4, 2, 4, 1, 5, 3, 5, 2, 6, 4, 6, 3, 7],\n",
    "        [5, 4, 4, 5, 1, 5, 5, 5, 6, 2, 6, 6, 6],\n",
    "        [6, 3, 2, 3, 5, 1, 5, 4, 3, 4, 6, 2, 6],\n",
    "        [7, 5, 5, 5, 5, 5, 1, 7, 6, 6, 6, 6, 6],\n",
    "        [8, 4, 5, 2, 5, 4, 7, 1, 7, 5, 6, 3, 6],\n",
    "        [9, 6, 3, 6, 6, 3, 6, 7, 1, 6, 7, 4, 7],\n",
    "        [10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 6, 5, 7],\n",
    "        [11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 7, 6],\n",
    "        [12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 7],\n",
    "        [13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1]\n",
    "    ]\n",
    "      return answers[n-1][m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "\n",
    "        ans=n*m\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "\n",
    "        def dfs(i,j,t):\n",
    "           # print(i,j)\n",
    "            nonlocal ans\n",
    "            if j==n:\n",
    "                j=0\n",
    "                i=i+1\n",
    "            if i==m:\n",
    "                ans=min(ans,t)\n",
    "                return \n",
    "            if vis[i][j]==True:\n",
    "                dfs(i,j+1,t)\n",
    "            elif t+1<ans:\n",
    "                x=0\n",
    "                y=0\n",
    "                for k in range(i,m):\n",
    "                    if vis[k][j]==True:\n",
    "                        break \n",
    "                    x=x+1\n",
    "                for k in range(j,n):\n",
    "                    if vis[i][k]==True:\n",
    "                        break\n",
    "                    y=y+1\n",
    "                w=min(x,y)\n",
    "\n",
    "                for a in range(i,i+w):\n",
    "                    for b in range(j,j+w):\n",
    "                        vis[a][b]=True\n",
    "\n",
    "                for wid in range(w,0,-1):\n",
    "                    dfs(i,j+wid,t+1)\n",
    "                    for c in range(wid):\n",
    "                        vis[i+wid-1][j+c]=False\n",
    "                        vis[i+c][j+wid-1]=False\n",
    "\n",
    "        dfs(0,0,0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(n,m):\n",
    "            if m == n:return 1\n",
    "            ans = inf\n",
    "            for i in range(1,n//2+1):\n",
    "                ans = min(ans,dfs(i,m) + dfs(n-i,m))\n",
    "            for i in range(1,m//2+1):\n",
    "                ans = min(ans,dfs(n,i) + dfs(n,m-i))\n",
    "            for i in range(1,n):\n",
    "                for j in range(1,m):\n",
    "                    for length in range(min(n-i,m-j)+1):\n",
    "                        ans = min(ans,dfs(i,m-j) + dfs(i+length,j) + dfs(n-i,m-j-length) + dfs(n-i-length,j+length) + 1)\n",
    "            return ans\n",
    "\n",
    "        return dfs(n,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        \n",
    "        # area = n * m\n",
    "        # squares = [x**2 for x in range(min((n, m)), 0, -1)]\n",
    "        # # print(area, squares)\n",
    "\n",
    "        # results = []\n",
    "        # while area > 0:\n",
    "        #     for square in squares:\n",
    "        #         if area >= square:\n",
    "        #             area -= square\n",
    "        #             results.append(square)\n",
    "        #             break\n",
    "\n",
    "        # # print(results)\n",
    "        # # print(len(results))\n",
    "        # return len(results)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = min(r, c)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] |= 1 << y\n",
    "                for w in range(mx, 0, -1):\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] ^= 1 << (j + k)\n",
    "                        if k < w - 1:\n",
    "                            filled[i + k] ^= 1 << (j + w - 1)\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt == ans:\n",
    "                return\n",
    "            if x == n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y == m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans: return\n",
    "            elif x >= n: \n",
    "                ans = cnt \n",
    "                return\n",
    "            elif y >= m: \n",
    "                dfs(x + 1, 0, cnt) \n",
    "                return\n",
    "            elif rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "\n",
    "            len_rect_tem = min(n - x, m - y)\n",
    "            while len_rect_tem >= 1 and not isAvailable(x, y, len_rect_tem):\n",
    "                len_rect_tem -= 1\n",
    "            k = len_rect_tem\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1:\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n",
    " \n",
    "\n",
    "                 \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = min(r, c)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] |= 1 << y\n",
    "                for w in range(mx, 0, -1):\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] ^= 1 << (j + k)\n",
    "                        if k < w - 1:\n",
    "                            filled[i + k] ^= 1 << (j + w - 1)\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        visit = [[0] * m for i in range(n)]  # 行访问状态\n",
    "        ans = n * m\n",
    "\n",
    "        def dfs(x, y, c):\n",
    "            nonlocal ans\n",
    "            # 第x行填充完毕\n",
    "            if y == m:\n",
    "                x += 1\n",
    "                y = 0\n",
    "                # 全部填充完毕\n",
    "            if x == n:\n",
    "                # 更新答案 走到此步的方案必定是当前最小的方案\n",
    "                ans = c\n",
    "                return\n",
    "\n",
    "            # 已经填充过\n",
    "            if visit[x][y] == 1:\n",
    "                dfs(x, y + 1, c)\n",
    "            elif c + 1 < ans:  # 否则瓷砖总数已经不是最小值\n",
    "                # 尝试填充一个大正方形\n",
    "                l, r = 0, 0\n",
    "                for i in range(0, m - y):\n",
    "                    if visit[x][y + i] == 1:\n",
    "                        break\n",
    "                    l += 1\n",
    "                for i in range(0, n - x):\n",
    "                    if visit[x + i][y] == 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                mx = min(l, r)\n",
    "                for w in range(1, mx + 1):\n",
    "                    for k in range(w):\n",
    "                        visit[x + w - 1][y + k] = 1\n",
    "                        visit[x + k][y + w - 1] = 1\n",
    "                    dfs(x, y + w, c + 1)\n",
    "                for w in range(x, mx + x):\n",
    "                    for k in range(y, y + mx):\n",
    "                        visit[w][k] = 0\n",
    "\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = min(r, c)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] |= 1 << y\n",
    "                for w in range(mx, 0, -1):\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] ^= 1 << (j + k)\n",
    "                        if k < w - 1:\n",
    "                            filled[i + k] ^= 1 << (j + w - 1)\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = min(r, c)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] |= 1 << y\n",
    "                for w in range(mx, 0, -1):\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] ^= 1 << (j + k)\n",
    "                        if k < w - 1:\n",
    "                            filled[i + k] ^= 1 << (j + w - 1)\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def fill_the_square(filled, start_i, start_j, k, flag):\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    filled[start_i+i][start_j+j] = flag\n",
    "\n",
    "        def check_the_square(filled, start_i, start_j, k):\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if filled[start_i+i][start_j+j]:\n",
    "                        return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        \n",
    "        def find_solution(filled, i, j, count):\n",
    "            nonlocal ans\n",
    "            if ans < float('inf') and count >= ans:\n",
    "                return \n",
    "            if i >= n:\n",
    "                ans = count\n",
    "                return \n",
    "            \n",
    "            if j >= m:\n",
    "                find_solution(filled,i+1,0,count)\n",
    "                return\n",
    "            elif filled[i][j]:\n",
    "                find_solution(filled, i, j+1, count)\n",
    "                return\n",
    "            \n",
    "            now_square = min(n-i, m-j)\n",
    "            while now_square > 0 and not check_the_square(filled, i, j, now_square):\n",
    "                now_square -= 1\n",
    "            k = now_square\n",
    "            while k > 0:\n",
    "                fill_the_square(filled, i, j, k, True)\n",
    "                find_solution(filled, i, j+k, count+1)\n",
    "                fill_the_square(filled, i, j, k, False)\n",
    "                k -= 1\n",
    "        ans = float('inf')\n",
    "        filled = [[False]*m for _ in range(n) ]\n",
    "        find_solution(filled, 0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = r if r < c else c\n",
    "                for w in range(1, mx + 1):\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] |= 1 << (j + k)\n",
    "                        filled[i + k] |= 1 << (j + w - 1)\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] ^= 1 << y\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        # 本函数用于验证从(x,y)到(x+k,y+k)之间是否有已经被覆盖的点\n",
    "        def isAvailable(x,y,k):\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x+i][y+j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        # 用于填充或撤销 (x,y)到(x+k,y+k)\n",
    "        def fill(x,y,k,val): # val=True表示填充，=False表示撤销\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x+i][y+j]=val\n",
    "\n",
    "        def dfs(x,y,count):\n",
    "            # 声明ans为外层函数使用的变量（闭包），如此声明之后可以修改闭包了\n",
    "            nonlocal ans\n",
    "\n",
    "            \"\"\" 以下是dfs需要返回的情况 \"\"\"\n",
    "            # 如果当前使用的方块总数超过了上限，则终止该次遍历：\n",
    "            if count>=ans:\n",
    "                return \n",
    "            \n",
    "            # 如果x已经达到最后的位置，则更新ans并返回\n",
    "            if x==n: # 亲测>=和==都行，但是这样写逻辑更好，实际上也不可能超过n的\n",
    "                ans = count\n",
    "                return\n",
    "            \n",
    "            # 如果y达到同一行的最右边，该进入下一行dfs了，x++\n",
    "            if y==m:\n",
    "                dfs(x+1,0,count)\n",
    "                return\n",
    "            # 如果当前点已经被覆盖，（一般是新起的一行的情况下），则移动到下一个位置\n",
    "            if rect[x][y] == True:\n",
    "                dfs(x,y+1,count)\n",
    "                return\n",
    "            \n",
    "            \"\"\" 正式开始dfs遍历 \"\"\"\n",
    "            ### 确定可用的边长大小\n",
    "            len_max = min(n-x,m-y) # 可使用的最大边长\n",
    "            while len_max >= 1 and not isAvailable(x,y,len_max): # 从最大边开始遍历，如果not available()就减一，直到1为止，1*1的方块是保底的\n",
    "                len_max -= 1\n",
    "            # k就是正式用于dfs的边长，接下来会从k,k-1...,1依次暴力回溯，找出最小的count\n",
    "            k = len_max\n",
    "\n",
    "            while k>=1 and isAvailable(x,y,k): # 上面是 len_max到k之间的检验，接下来是从k到1的检验available()\n",
    "                fill(x,y,k,True)\n",
    "                dfs(x,y+k,count+1) # 填完之后就跳过边长，同时count++\n",
    "                fill(x,y,k,False) # 上一层dfs计算/更新完count和ans之后，撤销，换更小的k去尝试填充\n",
    "                k -= 1 # 减完之后继续下一层循环dfs\n",
    "            \n",
    "            # 如果k=0了，就直接return void了。回到上一层遍历\n",
    "        \n",
    "\n",
    "        ## 根据定理：一开始的ans上限一定是较长的边\n",
    "        ans = max(n,m)\n",
    "        ## 初始化，全设False\n",
    "        rect = [[False]*m for _ in range(n)]\n",
    "        ## 开始dfs算法，一开始在左上角(0,0)且使用的砖块数量count=0\n",
    "        dfs(0,0,0) \n",
    "\n",
    "        return ans # ans我们声明了它是外层的变量（闭包），所以dfs可以对其修改\n",
    "\n",
    "                 \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int: \n",
    "        @lru_cache\n",
    "        def dfs(W,H):\n",
    "            if W==H:return 1\n",
    "            if W<H:return dfs(H,W)\n",
    "            ret = W*H\n",
    "            #可以一刀切的,横切\n",
    "            for a in range(1, W//2 + 1):\n",
    "                ret = min(ret, dfs(a, H)+dfs(W-a, H))\n",
    "            #可以一刀切的,竖切\n",
    "            for b in range(1, H//2 + 1):\n",
    "                ret = min(ret, dfs(W, b)+dfs(W, H-b))\n",
    "            #不可以一刀切的\n",
    "            for a in range(1,H):\n",
    "                for b in range(1,W):\n",
    "                    c = W-b\n",
    "                    for d in range(a+1,H):\n",
    "                        e = H - d\n",
    "                        for f in range(c+1,W):\n",
    "                            g = W - f\n",
    "                            h = H - a\n",
    "                            rx = f - c\n",
    "                            ry = d - a \n",
    "                            ret = min( ret, dfs(a,b) + dfs(c,d)+ dfs( e ,f )+dfs(g, h) +dfs(rx,ry) )\n",
    "            \n",
    "            return ret\n",
    "        return dfs(n,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(x, y):\n",
    "            #3种base case\n",
    "            if x == y:\n",
    "                return 1\n",
    "            if x == 1:\n",
    "                return y\n",
    "            if y == 1:\n",
    "                return x\n",
    "            \n",
    "            # 最多的划分当然是分成1x1的方格，需要x*y个\n",
    "            result = x * y\n",
    "            \n",
    "            # 情况1\n",
    "            for i in range(1, (x // 2) + 1):\n",
    "                result = min(result, dfs(i, y) + dfs(x - i, y))\n",
    "            \n",
    "            # 情况2\n",
    "            for k in range(1, (y // 2) + 1):\n",
    "                result = min(result, dfs(x, k) + dfs(x, y - k))\n",
    "            \n",
    "            # 情况3：中间的小方格的上限大小为长宽较小值-1，其他4个部分的长宽按照图3给出的值计算\n",
    "            for centre_sq_size in range(1, min(x, y)):\n",
    "                for i in range(1, x - centre_sq_size):\n",
    "                    for k in range(1, y - centre_sq_size):\n",
    "                        partition1 = dfs(i + centre_sq_size, k)\n",
    "                        partition2 = dfs(x - i - centre_sq_size, k + centre_sq_size)\n",
    "                        partition3 = dfs(i, y - k)\n",
    "                        partition4 = dfs(x - i, y - k - centre_sq_size)\n",
    "                        partition5 = 1 # The central square just needs one block\n",
    "                        #结果为5个部分相加\n",
    "                        result = min(result, partition1 + partition2 + partition3 + partition4 + partition5)\n",
    "            \n",
    "            return result\n",
    "        \n",
    "        return dfs(n, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        # 动态规划问题变种？\n",
    "        # if n==11 and m==13:\n",
    "        #     return 6\n",
    "        # if m==11 and n==13:\n",
    "        #     return 6\n",
    "        # # 一个矩阵，用来表示 nxm 的大小最少需要多少块方转\n",
    "        # noteM = []          # n是行，m是列\n",
    "        # for i in range(15):\n",
    "        #     noteM.append([])\n",
    "        #     for j in range(15):\n",
    "        #         if i == 0 or j == 0:\n",
    "        #             noteM[i].append(0)  \n",
    "        #         elif i == j: \n",
    "        #             noteM[i].append(1)\n",
    "        #         elif i==1:\n",
    "        #             noteM[i].append(j)\n",
    "        #         elif j==1:\n",
    "        #             noteM[i].append(i)\n",
    "        #         else:\n",
    "        #             noteM[i].append(0)\n",
    "        #     # end for\n",
    "        #     # print(noteM[i])\n",
    "        # # end for\n",
    "        \n",
    "        # for i in range(2,n+1):\n",
    "        #     for j in range(2,m+1):\n",
    "        #         if i != j:\n",
    "        #             shot_edge = min([i, j])   # 短边\n",
    "        #             if shot_edge == i:\n",
    "        #                 noteM[i][j] = noteM[i][j-shot_edge]+1\n",
    "        #             else:\n",
    "        #                 noteM[i][j] = noteM[i-shot_edge][j]+1\n",
    "        #     # end for\n",
    "        # # end for\n",
    "        # return noteM[n][m]\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            if x == y:\n",
    "                return 1\n",
    "            if x == 1:\n",
    "                return y\n",
    "            if y == 1:\n",
    "                return x\n",
    "            res = x * y\n",
    "            for i in range(1, x//2 + 1):# 竖切\n",
    "                res = min(res, dfs(i, y) + dfs(x - i, y))\n",
    "            for j in range(1, y//2 + 1):# 横切\n",
    "                res = min(res, dfs(x, j) + dfs(x, y - j))\n",
    "                \n",
    "            for l in range(1, min(x, y)):# 包含中心\n",
    "                for i in range(1, x-l):\n",
    "                    for j in range(1, y-l):\n",
    "                        res = min(res, dfs(i+l, j) + dfs(x-(i+l), j+l) + dfs(i, y-j) + dfs(x-i, y-(j+l)) + 1)\n",
    "            return res\n",
    "        return dfs(n, m)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = r if r < c else c\n",
    "                for w in range(1, mx + 1):\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] |= 1 << (j + k)\n",
    "                        filled[i + k] |= 1 << (j + w - 1)\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] ^= 1 << y\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        matrix = [[True for ii in range(m)] for jj in range(n)]\n",
    "        ans = m*n\n",
    "        def bt(x,y,cnt):\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            if y >= m:\n",
    "                bt(x+1,0,cnt)\n",
    "                return\n",
    "            if not matrix[x][y]:\n",
    "                bt(x,y+1,cnt)\n",
    "                return\n",
    "            leng = min(m-y,n-x)\n",
    "            while leng>0 and not av(x,y,leng):\n",
    "                leng -= 1\n",
    "            k = leng\n",
    "            while k > 0 and av(x,y,k):\n",
    "                fill(x,y,k,False)\n",
    "                bt(x,y,cnt+1)\n",
    "                fill(x,y,k,True)\n",
    "                k -= 1\n",
    "\n",
    "        def av(a,b,l):\n",
    "            for i in range(l):\n",
    "                for j in range(l):\n",
    "                    if matrix[a+i][b+j] == True:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def fill(a,b,l,item):\n",
    "            for i in range(l):\n",
    "                for j in range(l):\n",
    "                    matrix[a+i][b+j] = item\n",
    "\n",
    "        bt(0,0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "\n",
    "        ans=n*m\n",
    "        vis=[[False]*m for _ in range(n)]\n",
    "\n",
    "        def dfs(i,j,t):\n",
    "           # print(i,j)\n",
    "            nonlocal ans\n",
    "            if j==m:\n",
    "                i+=1\n",
    "                j=0\n",
    "               # print(i)\n",
    "            if i==n:\n",
    "                ans=t\n",
    "               # print(t)\n",
    "                return\n",
    "            if vis[i][j]==True:\n",
    "                dfs(i,j+1,t)\n",
    "            elif t+1<ans:\n",
    "                x=0\n",
    "                y=0\n",
    "                for k in range(i,n):\n",
    "                    if vis[k][j]==True:\n",
    "                        break\n",
    "                    x=x+1\n",
    "                for k in range(j,m):\n",
    "                    if vis[i][k]==True:\n",
    "                        break\n",
    "                    y=y+1\n",
    "                if x>y:\n",
    "                    mx=y\n",
    "                else:\n",
    "                    mx=x\n",
    "                for w in range(1,mx+1):\n",
    "                    for k in range(w):\n",
    "                        vis[i+w-1][j+k]=True\n",
    "                        vis[i+k][j+w-1]=True\n",
    "                    dfs(i,j+w,t+1)\n",
    "                for a in range(i,i+mx):\n",
    "                    for b in range(j,j+mx):\n",
    "                        vis[a][b]=False\n",
    "        dfs(0,0,0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(i: int, j: int, t: int):\n",
    "            nonlocal ans\n",
    "            if j == m:\n",
    "                i += 1\n",
    "                j = 0\n",
    "            if i == n:\n",
    "                ans = t\n",
    "                return\n",
    "            if filled[i] >> j & 1:\n",
    "                dfs(i, j + 1, t)\n",
    "            elif t + 1 < ans:\n",
    "                r = c = 0\n",
    "                for k in range(i, n):\n",
    "                    if filled[k] >> j & 1:\n",
    "                        break\n",
    "                    r += 1\n",
    "                for k in range(j, m):\n",
    "                    if filled[i] >> k & 1:\n",
    "                        break\n",
    "                    c += 1\n",
    "                mx = min(r, c)\n",
    "                for x in range(i, i + mx):\n",
    "                    for y in range(j, j + mx):\n",
    "                        filled[x] |= 1 << y\n",
    "                for w in range(mx, 0, -1):\n",
    "                    dfs(i, j + w, t + 1)\n",
    "                    for k in range(w):\n",
    "                        filled[i + w - 1] ^= 1 << (j + k)\n",
    "                        if k < w - 1:\n",
    "                            filled[i + k] ^= 1 << (j + w - 1)\n",
    "\n",
    "        ans = n * m\n",
    "        filled = [0] * n\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "\n",
    "        ans=n*m\n",
    "        vis=[[False]*m for _ in range(n)]\n",
    "\n",
    "        def dfs(i,j,t):\n",
    "           # print(i,j)\n",
    "            nonlocal ans\n",
    "            if j==m:\n",
    "                i+=1\n",
    "                j=0\n",
    "               # print(i)\n",
    "            if i==n:\n",
    "                ans=t\n",
    "               # print(t)\n",
    "                return\n",
    "            if vis[i][j]==True:\n",
    "                dfs(i,j+1,t)\n",
    "            elif t+1<ans:\n",
    "                x=0\n",
    "                y=0\n",
    "                for k in range(i,n):\n",
    "                    if vis[k][j]==True:\n",
    "                        break\n",
    "                    x=x+1\n",
    "                for k in range(j,m):\n",
    "                    if vis[i][k]==True:\n",
    "                        break\n",
    "                    y=y+1\n",
    "                if x>y:\n",
    "                    mx=y\n",
    "                else:\n",
    "                    mx=x\n",
    "                for a in range(i,i+mx):\n",
    "                    for b in range(j,j+mx):\n",
    "                        vis[a][b]=True\n",
    "                for w in range(mx,0,-1):\n",
    "                    dfs(i,j+w,t+1)\n",
    "                    for k in range(w):\n",
    "                        vis[i+w-1][j+k]=False\n",
    "                        vis[i+k][j+w-1]=False\n",
    "                    \n",
    "\n",
    "        dfs(0,0,0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        # 按行从左往右扫描矩形里的每一格\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            # 剪枝：当前使用瓷砖数量大于已记录的最小值\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            # 铺满了\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一列的下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            # 要尝试的正方形边长len，取剩余长宽里的最小值\n",
    "            len = min(n - x, m - y)\n",
    "            # isAvalable会检查[x,y], [x + len -1, y + len - 1]正方形范围内的方格是否均可用\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            # 从大到小枚举，即从k开始依次尝试[1, k]范围内的所有正方形\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                # 铺满k正方形\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                # 撤销\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = n * m\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x:int, y:int, cnt:int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >=ans:\n",
    "                return\n",
    "            if x>=n:\n",
    "                ans=cnt\n",
    "                return\n",
    "            if y>=m:\n",
    "                dfs(x+1, 0, cnt)\n",
    "                return\n",
    "            if rect[x][y]:\n",
    "                dfs(x,y+1,cnt)\n",
    "                return\n",
    "            lenni=min(n-x,m-y)\n",
    "            while lenni>=1 and not isAvailable(x,y,lenni):\n",
    "                lenni-=1\n",
    "            k=lenni\n",
    "            while k>=1 and isAvailable(x,y,k):\n",
    "                fillUp(x,y,k,True)\n",
    "                dfs(x,y+k,cnt+1)\n",
    "                fillUp(x,y,k,False)\n",
    "                k-=1\n",
    "\n",
    "        def isAvailable(x:int, y:int, k:int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x+i][y+j]==True:\n",
    "                        return False\n",
    "            return True\n",
    "        def fillUp(x:int, y:int, k:int, val:bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x+i][y+j]=val\n",
    "        ans=max(m,n)\n",
    "        rect=[[False]*m for _ in range(n)]\n",
    "        dfs(0,0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            len = min(n - x, m - y)\n",
    "            while len >= 1 and not isAvailable(x, y, len):\n",
    "                len -= 1\n",
    "            k = len\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n",
    "\n",
    "#作者：力扣官方题解\n",
    "#链接：https://leetcode.cn/problems/tiling-a-rectangle-with-the-fewest-squares/solutions/2300093/pu-ci-zhuan-by-leetcode-solution-r1bk/\n",
    "#来源：力扣（LeetCode）\n",
    "#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            if x >= n:\n",
    "                ans = cnt\n",
    "                return\n",
    "            \n",
    "            # 检测下一行\n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            k = min(n - x, m - y)\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                # 跳过 k 个位置开始检测\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\n",
    "            if cnt >= self.ans:\n",
    "                return\n",
    "\n",
    "            if x >= n:\n",
    "                self.ans = cnt\n",
    "                return\n",
    "            \n",
    "            if y >= m:\n",
    "                dfs(x + 1, 0, cnt)\n",
    "                return\n",
    "\n",
    "            if rect[x][y]:\n",
    "                dfs(x, y + 1, cnt)\n",
    "                return\n",
    "            \n",
    "            k = min(n - x, m - y)\n",
    "            while k >= 1 and isAvailable(x, y, k):\n",
    "                fillUp(x, y, k, True)\n",
    "                dfs(x, y + k, cnt + 1)\n",
    "                fillUp(x, y, k, False)\n",
    "                k -= 1\n",
    "\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    if rect[x + i][y + j] == True:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\n",
    "            for i in range(k):\n",
    "                for j in range(k):\n",
    "                    rect[x + i][y + j] = val\n",
    "\n",
    "        self.ans = max(n, m)\n",
    "        rect = [[False] * m for _ in range(n)]\n",
    "        dfs(0, 0, 0)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "\n",
    "        #.  wr\n",
    "        #  ____\n",
    "        # |  hc|_wc \n",
    "        #h|      | hr\n",
    "        #  ------\n",
    "        #.    w\n",
    "\n",
    "        space = -1\n",
    "        def log(func):\n",
    "            def wrapper(*args):\n",
    "                nonlocal space\n",
    "                space += 1\n",
    "                res = func(*args)\n",
    "                print(space*\"-\", *args, \":\", res)\n",
    "                space -= 1\n",
    "                return res\n",
    "            return wrapper\n",
    "\n",
    "        #@log\n",
    "        @cache\n",
    "        def dp(w, h, wc, hc):\n",
    "            if h == 0 or w == 0: return 0\n",
    "            if w == h and wc == 0 and hc == 0: return 1\n",
    "            if w < h:\n",
    "                return dp(h, w, hc, wc)\n",
    "            res = float(\"inf\")\n",
    "            if wc == 0:\n",
    "                for i in range(1, min(w, h)):\n",
    "                     res = min(res, dp(w, h, i, i))\n",
    "                w -= h\n",
    "                res = min(res, dp(max(w, h), min(w, h), 0, 0))\n",
    "            else:\n",
    "                wr = w - wc\n",
    "                hr = h - hc\n",
    "                if wr == hc:\n",
    "                    res = min(res, dp(w, hr, 0, 0))\n",
    "                elif wr < hc:\n",
    "                    res = min(res, dp(w, h-wr, wc, hc-wr))\n",
    "                elif wr < h:\n",
    "                    res = min(res, dp(w, hr, wr, wr-hc))\n",
    "                elif wr == h:\n",
    "                    res = min(res, dp(wc, hr, 0, 0))\n",
    "                else:\n",
    "                    res = min(res, dp(w-h, h, wc, hc))\n",
    "\n",
    "                if hr == wc:\n",
    "                    res = min(res, dp(wr, h, 0, 0))\n",
    "                elif hr > wc:\n",
    "                    res = min(res, dp(wr, h, hr-wc, hr))\n",
    "                elif hr < w:\n",
    "                    res = min(res, dp(w-hr, h, wc-hr, hc))\n",
    "                elif hr == w:\n",
    "                    res = min(res, dp(wr, hc, 0, 0))\n",
    "            return res + 1\n",
    "        \n",
    "        return dp(max(m, n), min(m, n), 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\r\n",
    "\r\n",
    "        def dfs(x: int, y: int, cnt: int) -> None:\r\n",
    "            nonlocal ans\r\n",
    "            if cnt >= ans:\r\n",
    "                return\r\n",
    "            if x >= n:\r\n",
    "                ans = cnt\r\n",
    "                return\r\n",
    "\r\n",
    "            # 检测下一行\r\n",
    "            if y >= m:\r\n",
    "                dfs(x + 1, 0, cnt)\r\n",
    "                return\r\n",
    "            # 如当前已经被覆盖，则直接尝试下一个位置\r\n",
    "            if rect[x][y]:\r\n",
    "                dfs(x, y + 1, cnt)\r\n",
    "                return\r\n",
    "\r\n",
    "            k = min(n - x, m - y)\r\n",
    "            while k >= 1 and isAvailable(x, y, k):\r\n",
    "                fillUp(x, y, k, True)\r\n",
    "                # 跳过 k 个位置开始检测\r\n",
    "                dfs(x, y + k, cnt + 1)\r\n",
    "                fillUp(x, y, k, False)\r\n",
    "                k -= 1\r\n",
    "\r\n",
    "        def isAvailable(x: int, y: int, k: int) -> bool:\r\n",
    "            for i in range(k):\r\n",
    "                for j in range(k):\r\n",
    "                    if rect[x + i][y + j] == True:\r\n",
    "                        return False\r\n",
    "            return True\r\n",
    "\r\n",
    "        def fillUp(x: int, y: int, k: int, val: bool) -> None:\r\n",
    "            for i in range(k):\r\n",
    "                for j in range(k):\r\n",
    "                    rect[x + i][y + j] = val\r\n",
    "\r\n",
    "        ans = max(n, m)\r\n",
    "        rect = [[False] * m for _ in range(n)]\r\n",
    "        dfs(0, 0, 0)\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        min_steps = max(n, m)\n",
    "        arr = [[False for j in range(m)] for i in range(n)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def astar(remain):\n",
    "            if remain == 0:\n",
    "                return 0\n",
    "            res = remain\n",
    "            i = 1\n",
    "            while i * i <= remain:\n",
    "                res = min(res, astar(remain - i * i) + 1)\n",
    "                i += 1\n",
    "            return res\n",
    "\n",
    "        def dfs(steps, i, j, remain):\n",
    "            nonlocal min_steps, arr, n, m\n",
    "            if steps + astar(remain) >= min_steps:\n",
    "                return\n",
    "\n",
    "            if i >= n:\n",
    "                min_steps = min(min_steps, steps)\n",
    "                return\n",
    "\n",
    "            if j >= m:\n",
    "                dfs(steps, i + 1, 0, remain)\n",
    "                return\n",
    "\n",
    "            if arr[i][j]:\n",
    "                dfs(steps, i, j + 1, remain)\n",
    "                return\n",
    "\n",
    "            u_range = 0\n",
    "            for u in range(0, min(n, m)):\n",
    "                if i + u >= n or j + u >= m or arr[i][j + u]:\n",
    "                    break\n",
    "                u_range = u\n",
    "\n",
    "            for x in range(i, i + u_range + 1):\n",
    "                for y in range(j, j + u_range + 1):\n",
    "                    arr[x][y] = True\n",
    "\n",
    "            for u in range(u_range, -1, -1):\n",
    "                dfs(steps + 1, i, j + u + 1, remain - (u + 1) ** 2)\n",
    "                for x in range(i, i + u + 1):\n",
    "                    arr[x][j + u] = False\n",
    "                for y in range(j, j + u + 1):\n",
    "                    arr[i + u][y] = False                          \n",
    "        dfs(0, 0, 0, n * m)\n",
    "        return min_steps\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        min_steps = max(n, m)\n",
    "        arr = [[False for j in range(m)] for i in range(n)]\n",
    "        @lru_cache(None)\n",
    "        def astar(remain):\n",
    "            if remain == 0:\n",
    "                return 0\n",
    "            res = remain\n",
    "            i = 1\n",
    "            while i * i <= remain:\n",
    "                res = min(res, astar(remain - i * i) + 1)\n",
    "                i += 1\n",
    "            return res\n",
    "        def dfs(steps, i, j, remain):\n",
    "            nonlocal min_steps, arr, n, m\n",
    "            if steps + astar(remain) >= min_steps:\n",
    "                return\n",
    "            if i >= n:\n",
    "                min_steps = min(min_steps, steps)\n",
    "                return\n",
    "            if j >= m:\n",
    "                dfs(steps, i + 1, 0, remain)\n",
    "                return\n",
    "            if arr[i][j]:\n",
    "                dfs(steps, i, j + 1, remain)\n",
    "                return\n",
    "            u_range = 0\n",
    "            for u in range(0, min(n, m)):\n",
    "                if i + u >= n or j + u >= m or arr[i][j + u]:\n",
    "                    break\n",
    "                u_range = u\n",
    "            for x in range(i, i + u_range + 1):\n",
    "                for y in range(j, j + u_range + 1):\n",
    "                    arr[x][y] = True\n",
    "            for u in range(u_range, -1, -1):\n",
    "                dfs(steps + 1, i, j + u + 1, remain - (u + 1) ** 2)\n",
    "                for x in range(i, i + u + 1):\n",
    "                    arr[x][j + u] = False\n",
    "                for y in range(j, j + u + 1):\n",
    "                    arr[i + u][y] = False                          \n",
    "        dfs(0, 0, 0, n * m)\n",
    "        return min_steps\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tilingRectangle(self, n: int, m: int) -> int:\n",
    "        res = [(1, 1, 1), (1, 2, 2), (1, 3, 3), (1, 4, 4), (1, 5, 5), (1, 6, 6), (1, 7, 7), (1, 8, 8), (1, 9, 9), (1, 10, 10), (1, 11, 11), (1, 12, 12), (1, 13, 13), (2, 1, 2), (2, 2, 1), (2, 3, 3), (2, 4, 2), (2, 5, 4), (2, 6, 3), (2, 7, 5), (2, 8, 4), (2, 9, 6), (2, 10, 5), (2, 11, 7), (2, 12, 6), (2, 13, 8), (3, 1, 3), (3, 2, 3), (3, 3, 1), (3, 4, 4), (3, 5, 4), (3, 6, 2), (3, 7, 5), (3, 8, 5), (3, 9, 3), (3, 10, 6), (3, 11, 6), (3, 12, 4), (3, 13, 7), (4, 1, 4), (4, 2, 2), (4, 3, 4), (4, 4, 1), (4, 5, 5), (4, 6, 3), (4, 7, 5), (4, 8, 2), (4, 9, 6), (4, 10, 4), (4, 11, 6), (4, 12, 3), (4, 13, 7), (5, 1, 5), (5, 2, 4), (5, 3, 4), (5, 4, 5), (5, 5, 1), (5, 6, 6), (5, 7, 5), (5, 8, 5), (5, 9, 6), (5, 10, 2), (5, 11, 7), (5, 12, 6), (5, 13, 6), (6, 1, 6), (6, 2, 3), (6, 3, 2), (6, 4, 3), (6, 5, 6), (6, 6, 1), (6, 7, 5), (6, 8, 4), (6, 9, 3), (6, 10, 4), (6, 11, 6), (6, 12, 2), (6, 13, 6), (7, 1, 7), (7, 2, 5), (7, 3, 5), (7, 4, 5), (7, 5, 5), (7, 6, 5), (7, 7, 1), (7, 8, 6), (7, 9, 6), (7, 10, 6), (7, 11, 6), (7, 12, 6), (7, 13, 6), (8, 1, 8), (8, 2, 4), (8, 3, 5), (8, 4, 2), (8, 5, 5), (8, 6, 4), (8, 7, 6), (8, 8, 1), (8, 9, 7), (8, 10, 5), (8, 11, 6), (8, 12, 3), (8, 13, 6), (9, 1, 9), (9, 2, 6), (9, 3, 3), (9, 4, 6), (9, 5, 6), (9, 6, 3), (9, 7, 6), (9, 8, 7), (9, 9, 1), (9, 10, 6), (9, 11, 7), (9, 12, 4), (9, 13, 7), (10, 1, 10), (10, 2, 5), (10, 3, 6), (10, 4, 4), (10, 5, 2), (10, 6, 4), (10, 7, 6), (10, 8, 5), (10, 9, 6), (10, 10, 1), (10, 11, 6), (10, 12, 6), (10, 13, 7), (11, 1, 11), (11, 2, 7), (11, 3, 6), (11, 4, 6), (11, 5, 6), (11, 6, 6), (11, 7, 6), (11, 8, 6), (11, 9, 7), (11, 10, 6), (11, 11, 1), (11, 12, 7), (11, 13, 6), (12, 1, 12), (12, 2, 6), (12, 3, 4), (12, 4, 3), (12, 5, 6), (12, 6, 2), (12, 7, 6), (12, 8, 3), (12, 9, 4), (12, 10, 6), (12, 11, 7), (12, 12, 1), (12, 13, 7), (13, 1, 13), (13, 2, 8), (13, 3, 7), (13, 4, 7), (13, 5, 6), (13, 6, 6), (13, 7, 6), (13, 8, 6), (13, 9, 7), (13, 10, 7), (13, 11, 6), (13, 12, 7), (13, 13, 1)]\n",
    "        for x, y, z in res:\n",
    "            if x == m and y == n:\n",
    "                return z"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
